import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MyOrder {

    /*
    * 直接插入排序
    * 时间复杂度度O（N^2）
    * 空间复杂度O（1）
    * 稳定性：稳定
    * */
    public int[] insertOrder(int[] arr){
        for (int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else break;
            }
//            while (j>=0&&arr[j]>tmp){
//                arr[j+1]=arr[j];
//                j--;
//            }
            arr[j+1]=tmp;
        }
        return arr;
    }
    /*
     * 希尔排序
     * 时间复杂度度O（N^2）
     * 空间复杂度O（1）
     * 稳定性：不稳定
     * */
    public int[] shellOrder(int[] arr){
        int gap=arr.length;
        while (gap>1){
            gap=gap/2;
            shell(arr,gap);
        }
        return arr;
    }
    private void shell(int[] arr, int gap) {
        for (int i=gap;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                }else break;
            }
            arr[j+gap]=tmp;
        }
    }
    /*
     * 直接选择排序
     * 时间复杂度度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     */
    public int[] selectOrder(int[] arr){
        for (int i=0;i<arr.length;i++){
            int min=i;
            for (int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            swap(i,min,arr);
        }
        return arr;
    }

    private void swap(int i, int j,int[] arr) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //双向选择排序
    public int[] selectOrder2(int[] arr){
        int i=0;
        int j=arr.length-1;
        while (i<j){
            int min=i;
            int max=i;
            for (int a=i+1;a<=j;a++){
                if(arr[a]<arr[min]){
                    min=a;
                }
                if(arr[a]>arr[max]){
                    max=a;
                }
            }
            swap(i,min,arr);
            //防止第一个元素就是最大元素
            if (max==i){
                max=min;
            }
            swap(j,max,arr);
            i++;
            j--;
        }
        return arr;
    }
    /*
     * 堆排序
     * 时间复杂度度:O(n*logn)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     */
    public void createHeap(int[] arr){
        for (int parent=(arr.length-1-1)/2;parent>=0;parent--){
            shiftdown(parent,arr.length,arr);

        }
    }

    private void shiftdown(int parent,int size,int[] arr) {
        int child=2*parent+1;
        while (child<size){
            if (child+1<size&&arr[child+1]>arr[child]){
                child=child+1;
            }
            if (arr[child]>arr[parent]){
                swap(child,parent,arr);
                parent=child;
                child=2*parent+1;
            }else break;
        }
    }

    public int[] heapOrder(int[] arr){
        createHeap(arr);
        int end=arr.length-1;
        while (end>0){
            swap(0,end,arr);
            shiftdown(0,end,arr);
            end--;
        }
    return arr;
    }

/**
     * 快速排序-》
     * 时间复杂度：
     *       最好的情况下：O(N*logN)
     *       最坏情况下：O(N^2) 逆序/有序
     * 空间复杂度：
     *       最好的情况下：O(logN)
     *       最坏情况下：O(N) 逆序/有序
     * 稳定性：不稳定
     */

    public int[] quickOrder(int[] arr){
        int p=0;
        quick(0,arr.length-1,arr);
        return arr;
    }


    private void quick(int start, int end, int[] arr) {
    if (start>=end){
        return;
    }
    int m=mid(start,end, arr);
    swap(start,m,arr);
    if (end-start>=15){
        insertOrder(start,end,arr);
        return;
    }
    int p=partionHoare(start,end,arr);
    quick(start,p-1,arr);
    quick(p+1,end,arr);
    }
    public void insertOrder(int l,int r ,int[] arr){
        for (int i=l+1;i<=r;i++){
            int tmp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else break;
            }
//            while (j>=0&&arr[j]>tmp){
//                arr[j+1]=arr[j];
//                j--;
//            }
            arr[j+1]=tmp;
        }

    }
    public  int mid(int l,int r,int[] arr){
       int mid=(l+r)/2;
       if (arr[l]<arr[r]){
           if(arr[mid]<arr[l]){
               return l;
           }else if (arr[mid]>arr[r]){
               return r;
           }else {
               return mid;
           }
       }else {
           //arr[l]>=arr[r]
           if (arr[mid]>arr[l]){
               return l;
           }else if (arr[mid]<arr[r]){
               return r;
           }else {
               return mid;
           }

       }
    }
    public int partionHoare(int l,int r,int[] arr){
        int tmp=l;
        while (l<r){
            while (l<r&&arr[l]<arr[tmp]){
                l++;
            }
            while (r>l&&arr[r]>arr[tmp]){
                r--;
            }
            swap(l,r,arr);
        }
        //l==r
        swap(l,tmp,arr);
        return l;
    }
    public int partitionHole(int l,int r,int[] arr){
        int tmp=arr[l];
        while (l<r){
            if (l<r&&arr[r]>tmp){
                r--;
            }
            arr[l]=arr[r];
            if (l<r&&arr[l]<tmp){
                l++;
            }
            arr[r]=arr[l];
        }
        arr[l]=tmp;
        return l;

    }
    private  int partition( int left, int right,int[] array) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(cur,prev,array);
            }
            cur++;
        }
        swap(prev,left,array);
        return prev;
//        int prev=left;
//        int cur=left+1;
//        while (cur<=right){
//           if (array[cur]<array[left]){
//               if (prev+1!=cur){
//                   prev++;
//                   //swap(prev,cur,array);
//               }
//               swap(prev,cur,array);
//           }
//           cur++;
//        }
//        swap(prev,left,array);
//        return prev;
    }
    public int[] quickOrderNor(int[] arr){
        Stack<Integer> stack=new Stack<>();
        int s=0;
        int e=arr.length-1;
        int pivot=partitionHole(s,e,arr);
        if (pivot-1>s){
            stack.push(s);
            stack.push(pivot-1);
        }
        if (e-1>pivot){
            stack.push(pivot+1);
            stack.push(e);
        }
        while (!stack.isEmpty()){
             e=stack.pop();
             s=stack.pop();
             pivot=partitionHole(s,e,arr);
            if (pivot-1>s){
                stack.push(s);
                stack.push(pivot-1);
            }
            if (e-1>pivot){
                stack.push(pivot+1);
                stack.push(e);
            }
        }
    return arr;
    }
/*
* 归并排序
*时间复杂度：O(N*logN)
*空间复杂度：O(logN)
* 稳定性：稳定
* */

    public int[] mergeOrder(int[] arr){
        mergeFun(0,arr.length-1,arr);
        return arr;
    }
    public void mergeFun(int l,int r,int[] arr){
        if (l>=r){
            return;
        }
        int mid=(l+r)/2;
        mergeFun(l,mid,arr);
        mergeFun(mid+1,r,arr);
        //归
        merge(l,r,mid,arr);

    }
    private void merge(int l, int r,int mid ,int[] arr) {
        int s1=l;
        int e1=mid;
        int s2=mid+1;
        int e2=r;
        int[] tmp=new int[r-l+1];
        int i=0;
        while (s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                tmp[i]=arr[s1];
                i++;
                s1++;
            }else {
                tmp[i]=arr[s2];
                i++;
                s2++;
            }
        }
        while (s1<=e1){
            tmp[i]=arr[s1];
            i++;
            s1++;
        }
        while (s2<=e2){
            tmp[i]=arr[s2];
            i++;
            s2++;
        }
        for (int j=0;j<tmp.length;j++){
            arr[j+l]=tmp[j];
        }

    }
    public int[] Buble(int[] arr){
        boolean flag=true;
        for(int i=0;i<arr.length-1;i++){
            for (int j=0;j<arr.length-i-1;j++){
                if (arr[j]>arr[j+1]){
                    swap(j,j+1,arr);
                    flag=false;
                }
            }
            if (flag){
                return arr;
            }
        }
        return arr;
    }
    //计数排序
    public int[] countOrder(int[] arr){
        int max=arr[0];
        int min=arr[0];
        for (int i=0;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        for (int i=0;i<arr.length;i++){
            if(arr[i]<min){
                min=arr[i];
            }
        }
        int[] tmp=new int[max-min+1];
        for (int i=0;i<arr.length;i++){
            tmp[arr[i]-min]++;
        }
//写回arr
//        Queue<Integer> queue=new LinkedList<>();
//        for (int i=0;i<tmp.length;i++){
//            while (tmp[i]!=0){
//                queue.offer(i);
//                tmp[i]--;
//            }
//        }
//        int size=queue.size();
//        for (int i=0;i<arr.length;i++){
//            queue.poll();
//        }
        int index=0;
        for (int i=0;i<tmp.length;i++){
            while (tmp[i]>0){
                arr[index]=i+min;
                index++;
                tmp[i]--;
            }
        }
        return arr;
    }

}

